Legendre's conjecture, proposed by

Adrien-Marie Legendre Adrien-Marie Legendre (; ; 18 September 1752 – 9 January 1833) was a French mathematician who made numerous contributions to mathematics. Well-known and important concepts such as the Legendre polynomials and Legendre transformation are named ...

, states that there is a

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

between

n^2

and

(n+1)^2

for every

positive integer In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...

n

. The

conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...

is one of

Landau's problems At the 1912 International Congress of Mathematicians, Edmund Landau listed four basic problems about prime numbers. These problems were characterised in his speech as "unattackable at the present state of mathematics" and are now known as Landau ...

(1912) on prime numbers; , the conjecture has neither been proved nor disproved.

Prime gaps

If Legendre's conjecture is true, the gap between any prime ''p'' and the next largest prime would be

O(\sqrt p)

, as expressed in

big O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...

. It is one of a family of results and conjectures related to

prime gap A prime gap is the difference between two successive prime numbers. The ''n''-th prime gap, denoted ''g'n'' or ''g''(''p'n'') is the difference between the (''n'' + 1)-th and the ''n''-th prime numbers, i.e. :g_n = p_ - p_n.\ W ...

s, that is, to the spacing between prime numbers. Others include

Bertrand's postulate In number theory, Bertrand's postulate is a theorem stating that for any integer n > 3, there always exists at least one prime number p with :n < p < 2n - 2. A less restrictive formulation is: for every

n > 1

, there is always ...

, on the existence of a prime between

n

and

2n

, Oppermann's conjecture on the existence of primes between

n^2

n(n+1)

, and

(n+1)^2

, Andrica's conjecture and

Brocard's conjecture In number theory, Brocard's conjecture is the conjecture that there are at least four prime numbers between (''p'n'')2 and (''p'n''+1)2, where ''p'n'' is the ''n''th prime number, for every ''n'' ≥ 2. The conjecture is named after Hen ...

on the existence of primes between squares of consecutive primes, and

Cramér's conjecture In number theory, Cramér's conjecture, formulated by the Swedish mathematician Harald Cramér in 1936, is an estimate for the size of gaps between consecutive prime numbers: intuitively, that gaps between consecutive primes are always small, and t ...

that the gaps are always much smaller, of the order

(\log p)^2

. If Cramér's conjecture is true, Legendre's conjecture would follow for all sufficiently large ''n''.

Harald Cramér Harald Cramér (; 25 September 1893 – 5 October 1985) was a Swedish mathematician, actuary, and statistician, specializing in mathematical statistics and probabilistic number theory. John Kingman described him as "one of the giants of statist ...

also proved that the

Riemann hypothesis In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...

implies a weaker bound of

O(\sqrt p\log p)

on the size of the largest prime gaps. Plot of number of primes between consecutive squares

By the

prime number theorem In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying ...

, the expected number of primes between

n^2

and

(n+1)^2

is approximately

n/\ln n

, and it is additionally known that for

almost all In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...

intervals of this form the actual number of primes () is

asymptotic In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...

to this expected number. Since this number is large for large

n

, this lends credence to Legendre's conjecture. It is known that the prime number theorem gives an accurate count of the primes within short intervals, either unconditionally or based on the

, but the lengths of the intervals for which this has been proven are longer than the intervals between consecutive squares, too long to prove Legendre's conjecture.

Partial results

It follows from a result by Ingham that for all sufficiently large

n

, there is a prime between the consecutive ''cubes''

n^3

and

(n+1)^3

. Baker, Harman and Pintz proved that there is a prime in the interval

-x^,\,x /math> for all large x . A table of maximal prime gaps shows that the conjecture holds to at least n^2=4\cdot10^, meaning n=2\cdot10^9 . .

Notes

References

External links

* Conjectures about prime numbers Squares in number theory Unsolved problems in number theory {{Numtheory-stub